package org.example.myleet.p576;

import java.util.*;

public class Solution {
    private static final int[][] DIRECTIONS = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    static class Point {
        int row;
        int col;

        public Point(int row, int col) {
            this.row = row;
            this.col = col;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Point point = (Point) o;
            return row == point.row &&
                    col == point.col;
        }

        @Override
        public int hashCode() {
            return Objects.hash(row, col);
        }
    }

    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        int MOD = 1000000007;
        long count = 0L;
        //记录当前每个点可到达的方案数量
        long[][] dp = new long[m][n];
        //初始化，初始位置即有1种方案
        dp[startRow][startColumn] = 1L;
        //BFS，记录下一次移动时涉及到的点
        Queue<Point> queue = new LinkedList<>();
        //初始位置的点入队
        queue.offer(new Point(startRow, startColumn));
        //总共循环maxMove-1次，模拟球的所有运动
        for (int move = 0; move < maxMove; ++move) {
            //遍历当前回合会运动到的所有点
            int queueSize = queue.size();
            //用于去重剪枝，优化时可以将这个替换成数组记录需要剪枝的点
            Set<Point> existPoint = new HashSet<>();
            for (int i = 0; i < queueSize; ++i) {
                //本回合，球可能到达的某个点
                Point point = queue.poll();
                for (int[] direction : DIRECTIONS) {
                    //然后模拟球下一回合每个方向会到达的点
                    int newR = point.row + direction[0];
                    int newC = point.col + direction[1];
                    if (newR < 0 || newR >= m || newC < 0 || newC >= n) {
                        //如果球出界了，记录一次方案数，因为方案数可能很大，注意要取余
                        count += dp[point.row][point.col];
                        count %= MOD;
                    } else {
                        //球没有出界，则更新到达位置的方案数，因为方案数可能很大，注意要取余
                        dp[newR][newC] += dp[point.row][point.col];
                        dp[newR][newC] %= MOD;
                        Point newPoint = new Point(newR, newC);
                        if (!existPoint.contains(newPoint)) {
                            //如果到达位置未曾入队，则入队
                            queue.offer(newPoint);
                            existPoint.add(newPoint);
                        }
                    }
                }
                //注意本回合的这个点已经用完，因此球不会在这个点，方案数重置为0
                dp[point.row][point.col] = 0;
            }
        }
        return (int) count;
    }
}
